#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>//包含deque和priority_queue
#include<list>
#include<vector>
#include<ctime>
#include<functional>//需要用到仿函数greater
using namespace std;

//stack和queue都是是适配器，没有迭代器
//所以stack遍历需要判断是否为空，打印栈顶的数据，然后一个个出栈
//queue遍历需要判断是否为空，打印队头的数据，然后一个个出队
void test_stack(){
	stack<int> st1;
	st1.push(1);
	st1.push(2);
	st1.push(3);
	st1.push(4);
	while (!st1.empty())
	{
		cout << st1.top() << " ";
		st1.pop();
	}
	cout << endl;

	stack<int,list<int> > st2;
	st2.push(10);
	st2.push(20);
	st2.push(30);
	st2.push(40);
	while (!st2.empty())
	{
		cout << st2.top() << " ";
		st2.pop();
	}
	cout << endl;
}

void test_queue(){
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);

	//stack是适配器，没有迭代器
	//所以遍历需要判断是否为空，打印栈顶的数据，然后一个个出栈
	while (!q.empty())
	{
		cout << q.front() << " ";
		q.pop();
	}
	cout << endl;

	queue<int,list<int>> qq;
	qq.push(1);
	qq.push(2);
	qq.push(3);
	qq.push(4);

	while (!qq.empty())
	{
		cout << qq.front() << " ";
		qq.pop();
	}
	cout << endl;
}

//测试双端队列和vector排序的效率
void test_deque(){
	deque<int> d;
	vector<int> v;
	const int n = 70000;
	int x;
	srand(time(0));
	for (size_t i = 0; i < n; i++)
	{
		x = rand();
		d.push_back(x);
		v.push_back(x);
	}
	size_t begin1 = clock();
	sort(d.begin(),d.end());
	size_t end1 = clock();

	size_t begin2 = clock();
	sort(v.begin(),v.end());
	size_t end2 = clock();

	cout << "deque:"<< end1 - begin1 << endl;
	cout << "vector:"<< end2 - begin2 << endl;
	
}

//容器适配器都不支持迭代器遍历，因为他们通常都包含一些特殊性质
//如果支持迭代器随便遍历，那他们无法很好的保持它的性质
void test_priority_queue(){
	priority_queue<int> pq;
	pq.push(3);
	pq.push(1);
	pq.push(4);
	pq.push(6);
	pq.push(2);

	//默认是大的优先级高
	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;

	//如果想变成小的优先级高，那就需要仿函数
	priority_queue<int,vector<int>, greater<int> > pq2;
	pq2.push(30);
	pq2.push(22);
	pq2.push(1);
	pq2.push(4);
	pq2.push(85);

	while (!pq2.empty())
	{
		cout << pq2.top() << " ";
		pq2.pop();
	}
	cout << endl;
}

//仿函数
template<class T>
struct myless{
	bool operator()(const T& x1, const T& x2){
		return x1 < x2;
	}
};

void test_less(){
	myless<int> lessFunc;
	int x1 = 2, x2 = 3;
	//lessFunc看上去是个函数，其实是个类对象
	cout << lessFunc(x1, x2) << endl;
}

int main(){
	//test_stack();
	//test_queue();
	//test_deque();
	//test_priority_queue();
	test_less();
	return 0;
}